package com.example.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * 单调栈
 *
 * 移除重复字母保持字典序最小
 * 1.核心维护字符最后出现位置
 */
public class Demo0316 {

    public static void main(String[] args) {

    }

    public static String removeDuplicateLetters(String s) {

        int len = s.length();
        Deque<Character> stack=new ArrayDeque<>(len);
        stack.addLast('a');
        Set<Character> set=new HashSet<>(len);
        int[] lastIndex =new int[26];
        for (int i = 0; i < len; i++) {
            lastIndex[s.charAt(i)-'a']=i;
        }

        for (int index = 0; index < len; index++) {

            char curChar = s.charAt(index);
            //1.最快判断 是否包含
            if (set.contains(s.charAt(index))){
                continue;
            }

            //2.考虑是否出栈
            while (stack.peekLast()>curChar && lastIndex[stack.peekLast()-'a']>index){
                Character character = stack.removeLast();
                set.remove(character);
            }

            //3.不包含，也无须出栈，直接入栈
            stack.addLast(curChar);
            set.add(curChar);
        }

        stack.removeFirst();
        StringBuilder sb=new StringBuilder();
        while (!stack.isEmpty()){
            sb.append(stack.removeFirst());
        }
        return sb.toString();
    }
}
